%%%-------------------------------------------------------------------
%%% File    : p5.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% 2520 is the smallest number that can be divided by each of the 
%%% numbers from 1 to 10 without any remainder.
%%% What is the smallest number that is evenly divisible by all of the 
%%% numbers from 1 to 20?
%%%
%%% Created :  1 Dec 2008 
%%%-------------------------------------------------------------------
-module(p5).

%% API
-compile(export_all).

solution(N) ->
    %If a number N is divisible by a number K, it is also divisible by all factors of K.
    %So we filter out the factors and only need to check if a number is divisible by the 
    %rest.
    List = reduce(lists:seq(2, N)),
    %list all prime factors for each number
    Factors = [factors(X)||X<-List],
    %To get the smallest number divisible by all numbers in the list
    %we just need to multiple all unique prime factors, raised by their
    %maximum powers
    %For example in [6, 8] 2 has a maximum power of 3 (8 = 2**3) and 3 has
    %a maximum power of 1, so (2**3)*(3**1) = 24 is the smallest divisible by
    %both.
    FactorTbl = max_count(Factors),
    ets:foldl(fun({X, Count}, Acc) -> Acc*math:pow(X, Count) end, 1, FactorTbl).

%Filters out all numbers that are factors of another number in the list
reduce(List) ->
    reduce(List, []).

reduce([], Acc) -> lists:reverse(Acc);
reduce([H|T], Acc) ->
    case divides(H, T) of
        true -> reduce(T, Acc);
        _ -> reduce(T, [H|Acc])
    end.
    
%Checks if a number is a factor of any of the numbers in the list
divides(_, []) ->
    false;
divides(X, [H|T]) ->
    (H rem X =:= 0) orelse divides(X, T).


%Returns a list of all prime factors of a number    
factors(N) ->
    factors(N, 2, []).

factors(0, _, Acc) -> Acc;
factors(N, I, Acc) when I > (N div 2)->
    [N|Acc];
factors(N, I, Acc) ->
    case N rem I =:= 0 of
        true ->
            factors(N div I, I, [I | Acc]);
        _ -> factors(N, I + 1, Acc)
    end.

%Finds the maximum count of each factor in the lists and
%returns an ETS table with the count mapped to the number
max_count(FactorLists) ->
    Tbl = ets:new(counted, []),
    lists:foreach(fun(I) -> max_count(I, Tbl) end, FactorLists),
    Tbl.
    
max_count(List, Tbl) ->
    max_count(List, null, 0, Tbl).

max_count([], _, _, Acc) ->
    Acc;
max_count([H|T], Prev, Count, Acc) -> 
    NewCount = case Prev =:= H of
                   true -> Count + 1;
                   _ -> 1
               end,
    Lookup = ets:lookup(Acc, H),
    case Lookup of
        [{H, N}] when NewCount > N ->
            %overwrite if it is greater than the old one
            ets:insert(Acc, {H, NewCount});
        [] ->
            ets:insert(Acc, {H, NewCount});
        _ -> void
    end,
    max_count(T, H, NewCount, Acc).
    

